#include<stdio.h>
#include<malloc.h>

typedef struct{int col,row;int* data;} mat;

void print_mat(const mat* m){
    int i,j;
    printf("<Matrix %dx%d>\n",m->row,m->col);
    for(i=0;i<m->col;i++){
        for(j=0;j<m->row;j++)printf("%d ",(m->data)[i*m->col+j]);
        putchar('\n');
    }
}

void dfs_adj_mat_non_recursive(const mat* m){
    // stack里的数字都是vis的坐标位置，都是从0开始数的，但是矩阵是从1开始数，要小心！
    int i,vis_count,ip,cur;
    int* vis = malloc(sizeof(int)*m->row);
    int* stack = malloc(sizeof(int)*m->row);
    int* exh = malloc(sizeof(int)*m->row); //exhaust
    for(i=0;i<m->row;i++)vis[i]=exh[i]=0;
    vis_count = 0; ip = 0;
    while(vis_count < m->row){
        if(ip==0){i=-1;while(vis[++i]);stack[ip++]=i;}//empty stack, randomly push one unvisited vertex
        cur = stack[ip-1];if(vis[cur]==0){printf("%d ",cur+1);vis[cur]=1;vis_count++;}
        for(i=exh[cur];i<m->row;i++){if(m->data[cur*m->col+i]==1 &&vis[i]==0){stack[ip++]=i;exh[cur]=i+1;break;}}
        if(i==m->row)ip--;
    }putchar('\n');
    free(vis); free(stack); free(exh);
}



int main(){
    // get adjacency matrix
    int i,j;
    printf("Enter verteice count: ");
    scanf("%d",&i);
    printf("Enter Matrix by rows:\n");
    mat A; A.row = i; A.col = i;
    A.data = malloc(sizeof(int)*A.row*A.col);
    for(i =0;i<A.row;i++){
        printf("Row #%d> ",i+1);
        for(j=0;j<A.col;j++){scanf("%d",A.data+i*A.col+j);}fflush(stdin);
    }
    printf("Get Adjacency matrix:\n");print_mat(&A);
    printf("dfs: ");dfs_adj_mat_non_recursive(&A);
    free(A.data);
}